package week_eight;

import java.util.ArrayList;
import java.util.List;

public class MinCostToConnectAllPoints_1584 {
    int[] fa;

    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        fa = new int[n];
        for (int i = 0; i < n; i++) fa[i] = i;
        // PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> a[2]-b[2]);
        List<int[]> edges = new ArrayList<>();

        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int dist = Math.abs(points[j][0] - points[i][0]) + Math.abs(points[j][1] - points[i][1]);
                edges.add(new int[]{i, j, dist});
            }

        edges.sort((a, b) -> a[2] - b[2]);

        int ans = 0;
        for (int[] edge : edges) {
            // int[] edge = q.poll();
            int x = edge[0];
            int y = edge[1];
            int z = edge[2];
            if (find(x) != find(y)) {
                ans += z;
                fa[find(x)] = find(y);
            }
        }

        return ans;

    }

    private int find(int x) {
        if (x == fa[x]) return x;
        return fa[x] = find(fa[x]);
    }
}
